const UUID = new class _UUID {
    private index = 0;

    public create(): string {
        if (this.index++ > 10000000) {
            this.index = 0;
        }
        return `${Date.now()}-${this.index}`;
    }
}

/**
 * 默认碰撞检测过滤器
 * @param rect 
 * @param other 
 */
function FilterHandle(rect: Rect, other: Rect, filter?: (rect: Rect, other: Rect) => boolean): boolean {
    if (rect.uuid === other.uuid) return false;
    return filter ? filter(rect, other) : rect.intersect(other);
}

const Indexs = [1 << 0, 1 << 1, 1 << 2, 1 << 3];
const Mix2Indexs = [Indexs[0] | Indexs[1], Indexs[1] | Indexs[2], Indexs[2] | Indexs[3], Indexs[0] | Indexs[3]];

export class Rect {
    private _uuid: string = '';

    private _x: number = 0;
    private _y: number = 0;
    private _width: number = 0;
    private _height: number = 0;

    private _xMid: number = 0;
    private _yMid: number = 0;

    private _xMax: number = 0;
    private _yMax: number = 0;

    public get uuid() {
        return this._uuid;
    }

    public get x() {
        return this._x;
    }
    public get y() {
        return this._y;
    }
    public get width() {
        return this._width;
    }
    public get height() {
        return this._height;
    }
    public get xMin() {
        return this._x;
    }
    public get xMid() {
        return this._xMid;
    }
    public get xMax() {
        return this._xMax;
    }
    public get yMin() {
        return this._y;
    }
    public get yMid() {
        return this._yMid;
    }
    public get yMax() {
        return this._yMax;
    }

    constructor(x: number, y: number, w: number, h: number, uuid?: string) {
        this._uuid = uuid || UUID.create();
        this.setPosAndSize(x, y, w, h);
    }

    public setPosAndSize(x: number, y: number, w: number, h: number) {
        this._x = x;
        this._y = y;
        this._width = w;
        this._height = h;

        this._xMax = this._x + this._width;
        this._yMax = this._y + this._height;

        this._xMid = this._x + this._width / 2;
        this._yMid = this._y + this._height / 2;
    }

    public setPositon(x: number, y: number) {
        this._x = x;
        this._y = y;

        this._xMax = x + this._width;
        this._yMax = y + this._height;

        this._xMid = x + this._width / 2;
        this._yMid = y + this._height / 2;
    }

    public setSize(w: number, h: number) {
        this._width = w;
        this._height = h;

        this._xMax = this._x + w;
        this._yMax = this._y + h;

        this._xMid = this._x + w / 2;
        this._yMid = this._y + h / 2;
    }

    /**
     * 测试自身矩形是否与rect矩形相交
     */
    public intersect(rect: Rect) {
        return rect.xMax >= this.xMin &&
            rect.xMin <= this.xMax &&
            rect.yMax >= this.yMin &&
            rect.yMin <= this.yMax;
    }

    /**
     * 测试自身矩形是否包含rect矩形
     */
    public contain(rect: Rect) {
        return this.xMin <= rect.xMax &&
            this.xMax >= rect.xMin &&
            this.yMin <= rect.yMax &&
            this.yMax >= rect.yMin;
    }
}

class QuadtreeChild {
    protected max_levels: number = 4;

    protected level: number = 0;
    protected bounds: Rect = null;
    protected rects: Rect[][] = [[], [], [], [], []];
    protected childs: QuadtreeChild[] = [];

    // 是否有效
    private _isValid = true;

    constructor(bounds: Rect, max_levels?: number, level?: number) {
        this.bounds = bounds;

        this.max_levels = max_levels || 4;

        this.level = level || 0;
    }

    public get isValid(): boolean {
        return this._isValid;
    };

    public get size(): number {
        let n = 0;
        for (let i = 0; i < this.childs.length; i++) {
            n += this.childs[i].size;
        }
        return n + this.rects.length;
    }

    /**
     * 分裂
     */
    protected split() {
        if (!this.childs.length) {
            const x = this.bounds.x;
            const y = this.bounds.y;
            const w = this.bounds.width / 2;
            const h = this.bounds.height / 2;
            const level = this.level + 1;
            this.childs.push(
                new QuadtreeChild(new Rect(x + w, y + h, w, h), this.max_levels, level),
                new QuadtreeChild(new Rect(x, y + h, w, h), this.max_levels, level),
                new QuadtreeChild(new Rect(x, y, w, h), this.max_levels, level),
                new QuadtreeChild(new Rect(x + w, y, w, h), this.max_levels, level)
            );
        }
    }


    /**
     * 获得所在象限
     */
    protected getIndexs(rect: Rect): number {
        //口口
        //口口
        let indexs = 0;

        const startInLeft = rect.xMin < this.bounds.xMid,
            startInTop = rect.yMax > this.bounds.yMid,
            endInRight = rect.xMax > this.bounds.xMid,
            endInBottom = rect.yMin < this.bounds.yMid;

        if (startInTop && endInRight) {
            indexs |= Indexs[0];
        }
        if (startInTop && startInLeft) {
            indexs |= Indexs[1];
        }
        if (startInLeft && endInBottom) {
            indexs |= Indexs[2];
        }
        if (endInRight && endInBottom) {
            indexs |= Indexs[3];
        }

        return indexs;
    }

    /**
     * 插入
     */
    protected insert(rect: Rect): QuadtreeChild {
        //口口|口口
        //口口|口口
        //--------
        //口口|口口
        //口口|口口

        // 获取与哪些象限相交
        const indexs = this.getIndexs(rect);
        // 交集index
        // const mixIndex = Mix2Indexs.indexOf(indexs) + 1;
        // 子集index
        const index = Indexs.indexOf(indexs);

        // 相交数为0或多余1个，直接存储在自身
        // 自身是最后一层，直接存储在自身
        if (index === -1 || this.level === this.max_levels) {
            this.rects[Mix2Indexs.indexOf(indexs) + 1].push(rect);
            return this;
        }

        // 分割子象限
        if (this.childs.length === 0) {
            this.split();
        }

        // 插入到子象限中
        return this.childs[index].insert(rect);
    }

    /**
     * 删除
     */
    protected remove(rectUuid: String): Rect {
        for (let index = 0, rects: Rect[] = null; index < this.rects.length; index++) {
            rects = this.rects[index];
            for (let i = 0, rect: Rect = null; i < rects.length; i++) {
                rect = rects[i];
                if (rect.uuid === rectUuid) {
                    return this.rects[index].splice(i, 1)[0];
                }
            }
        }

        return null;
    }

    /**
     * 检索
     * @param rect 检索区域
     * @param filter 过滤器
     */
    public retrieve(rect: Rect, filter?: (rect: Rect, other: Rect) => boolean, out?: Rect[]): Rect[] {
        //口口|口口
        //口口|口口
        //--------
        //口口|口口
        //口口|口口

        const result = out || [];

        // 获取rect与哪些象限相交
        const indexs = this.getIndexs(rect);

        // 自身存储的rect一定会被检索到
        for (let i = -1; i < Mix2Indexs.length; i++) {
            if (i >= 0 && !(Mix2Indexs[i] & indexs)) continue;

            for (let index = 0, rects = this.rects[i + 1], other: Rect = null; index < rects.length; index++) {
                other = rects[index];
                if (FilterHandle(rect, other, filter)) {
                    result.push(other);
                }
            }
        }

        // 自身是最后一层，没有子节点
        if (this.childs.length === 0 || this.level === this.max_levels) {
            return result;
        }

        // 都不相交
        if (indexs === 0) return result;

        // 组合子象限数据
        for (let index = 0, value = 0; index < Indexs.length; index++) {
            value = Indexs[index];

            if (!(value & indexs)) continue;
            this.childs[index].retrieve(rect, filter, result);
        }

        return result;
    };

    /**
     * 清空
     */
    protected clear() {
        for (let i = this.childs.length - 1; i >= 0; i--) {
            this.childs[i].clear();
        }

        this._isValid = false;
        this.rects.length = 0;
        this.childs.length = 0;
    }
}

export class Quadtree extends QuadtreeChild {
    private rectTree: Map<string, QuadtreeChild> = new Map();
    private rectInfo: Map<string, Rect> = new Map();

    constructor(bounds: Rect, max_levels?: number) {
        super(bounds, max_levels);
    }

    /**
     * 插入一个rect
     * @param rect 
     */
    public insert(rect: Rect): QuadtreeChild {
        const tree = super.insert(rect);

        if (!tree) return null;

        this.rectTree.set(rect.uuid, tree);
        this.rectInfo.set(rect.uuid, rect);

        return tree;
    }

    /**
     * 移除一个rect
     * @param uuid 
     */
    public remove(uuid: string): Rect {
        const tree = this.rectTree.get(uuid);

        if (!tree) return null;

        this.rectTree.delete(uuid);
        this.rectInfo.delete(uuid);

        if (tree === this) {
            return super.remove(uuid);
        }
        return super.remove.call(tree, uuid);
    }

    /**
     * 刷新一个rect
     * @param uuid 
     * @param data 
     */
    public refresh(uuid: string, data?: { x?: number, y?: number, width?: number, height?: number }): boolean {
        let rect: Rect = null;

        // 移除
        let tree = this.rectTree.get(uuid);
        if (!tree) return false;
        if (tree === this) {
            rect = super.remove(uuid);
        } else {
            rect = super.remove.call(tree, uuid);
        }

        // 失败返回
        if (!rect) {
            this.rectTree.delete(uuid);
            this.rectInfo.delete(uuid);
            return false
        };

        // 设置
        if (data) {
            const x = typeof data.x === 'undefined' ? rect.x : data.x;
            const y = typeof data.y === 'undefined' ? rect.y : data.y;
            const w = typeof data.width === 'undefined' ? rect.width : data.width;
            const h = typeof data.height === 'undefined' ? rect.height : data.height;
            rect.setPosAndSize(x, y, w, h);
        }

        // 重新添加
        tree = super.insert(rect);
        // 失败返回
        if (!tree) {
            this.rectTree.delete(uuid);
            this.rectInfo.delete(uuid);
            return false
        };
        this.rectTree.set(rect.uuid, tree);
        return true;
    }

    /**
     * 检索rect数组
     * @param rectOrUuid 
     * @param filter 
     */
    public retrieve(rectOrUuid: Rect | string, filter?: (rect: Rect, other: Rect) => boolean): Rect[] {
        if (typeof rectOrUuid === 'string') {
            const rect = this.rectInfo.get(rectOrUuid);
            if (!rect) return [];
            return super.retrieve(rect, filter, []);
        } else {
            return super.retrieve(rectOrUuid, filter), [];
        }
    }

    /**
     * 清理内存
     */
    public clear() {
        super.clear();
        this.rectTree.clear();
        this.rectInfo.clear();
    }
}